Dirichlet's Approximation Theorem

Theorem

Given a fixed integer \(Q \geq 2\), any real number \(\alpha\) can be approximated by the rational number \(\frac{p}{q}\) where

\[ \left|\alpha - \frac{p}{q}\right| < \frac{1}{qQ}\]

with \(\gcd(p, q) = 1\) and \(0 < q \leq Q\).

The proof is constructive.

Proof

For this proof we let \(\{\beta\} = \beta - \lfloor \beta \rfloor\), that is \(\{\beta\}\) denotes the "fractional" part of \(\beta\).

Consider the following values of \(\{k\alpha\}\) for \(k = 0, 1, \dots, Q\)

\[ \{0\}, \{\alpha\}, \{2\alpha\}, \{3\alpha\}, \dots, \{Q\alpha\}.\]

We will show that no two of these values differ by \(\frac{1}{Q}\).

Consider for \(i \in \{0, 1, 2, \dots, Q - 1\}\) the intervals:

\[ I_i = \left[\frac{i}{Q}, \frac{i + 1}{Q}\right).\]

We use these to partition the interval \([0, 1)\) into \(Q\) intervals of width \(\frac{1}{Q}\). Now, with \(Q + 1\) numbers of the form \(\{k\alpha\}\) by the pigeonhole principal at least two of these numbers fall into the same interval, and hence there exists distinct \(m, n\) such that

\[ \frac{1}{Q} > |\{m\alpha\} - \{n\alpha\}|.\]

Then expanding these fractional parts into their definition we have

\[\begin{align*} \frac{1}{Q} &> |\{m\alpha\} - \{n\alpha\}| \\ &= |(m\alpha - \lfloor m\alpha \rfloor) - (n\alpha - \lfloor n\alpha \rfloor)| \\ &= |m\alpha - \lfloor m\alpha \rfloor - n\alpha + \lfloor n\alpha \rfloor| \\ &= |\alpha(m - n) - (\lfloor m\alpha \rfloor - \lfloor n\alpha \rfloor)| \\ &= |m - n|\left|\alpha - \frac{\lfloor m\alpha \rfloor - \lfloor n\alpha \rfloor}{m - n}\right| \\ \end{align*}\]

and therefore

\[ \frac{1}{Q|m - n|} > \left|\alpha - \frac{\lfloor m\alpha \rfloor - \lfloor n\alpha \rfloor}{m - n}\right|.\]

Thus, with the choice \(q = |m - n|\) and \(p = \lfloor m\alpha \rfloor - \lfloor n\alpha \rfloor\) the desired inequality holds. The fact that \(0 < q \leq Q\) follows from the fact that \(m\) and \(n\) are distinct integers drawn from the set \(0, 1, \dots, Q\). If \(\gcd(p, q)\) is not equal to \(1\), the the desired inequality still holds \(p', q'\) which are constructed by taking out a common factor. Namely, with smaller \(q'\) the right hand side becomes bigger, and \(q'\) is still bounded above by \(Q\).